Batch 3 - Class 172 - Nim Games 2

• [Part of lesson plan below]

• "Count to 20" NIM Game
• Removing Pennies
• Breaking Chocolates
• What if you could continue to break even the piece of chocolate bar that has been broken up before?
• Answer: In this case, at every step you are creating one more piece, and the game will have exactly 47 turns. Hence the person who starts first will make the last break regardless of the sequence.
• Asymmetric Rook

• 20 digit number - Two players take turn writing a 20 digit number left to right. If the number is divisible by 3, Bob wins. Else Alice. When does who win? (Answer: If Bob starts, Bob loses. If Alice starts, Bob Wins)
• What if the number in this game is replaced from 3 to 15?
• What if you play this number in binary?
• Answer: If Bob goes second, then Bob wins by just replicating Alice's move. If Alice writes 0, Bob writes 0; if Alice writes 1, Bob writes 1. This ensures that each "block" is either 0 or 3, which are divisible by 3. If Bob starts, then Bob loses, because in the last turn, Alice has two options, only one of which can be divisible by 3.
• Multiplying to 1000 -  Alice calls out any integer between 2 and 9, Bob multiplies it by any integer between 2 and 9, then Alice multiplies the new number by any integer between 2 and 9, and so on. The player who first gets a number bigger than 1000 wins.
• Squares and Circles - In this game, one person plays Squares and the other plays Circles. Start with an initial row of circles and squares. On each turn, a player can either replace two adjacent identical objects with a square, or two adjacent dissimilar objects with a circle. The Square player wins if the last shape is a square and the Circles player wins if the last shape is a circle. 
• This is actually a problem of invariants. The parity of circles is an invariant in this game. So if the game started with even circles, the Square player wins, else the Circle player wins. You can play here http://www.cut-the-knot.org/SimpleGames/one_two.shtml

• Revision: Piles of counters
• What if we had two piles of 7 and 10 counters, and each player could take a match from either or both of the two piles (Person to remove the last penny wins)
• (Mott 178) There are three piles with 3,5 and 7 counters respectively in them. At each turn, a player may draw any number of counters from one pile (or all counters from one pile). Whoever draws the last wins. Who wins and how?
• Answer: Express number of counters in each pile as powers of 2 (so first pile has 1 and 2, second has 1 and 4, third has 1, 2 and 4). If a player leaves piles so that each power of 2 is present twice across all piles combined, they will win. So in this case, the first player wins by taking 1 from any pile.
• In solution, if kids don't understand binary, do it as per comment on https://plus.maths.org/content/play-win-nim - Each power of two must have a partner

• You have two kinds of packets of chocolates - ones that have 5 chocolates in them, and ones that have 7 chocolates in them. What is the largest number of chocolates you can't give away, assuming you can't open the packets to do so

• Empty and Divide -  (Ferguson (1998)) There are two boxes. Initially, one box contains m chips and the other contains n chips. Such a position is denoted by (m, n), where m > 0 and n > 0. The two players alternate moving. A move consists of emptying one of the boxes, and dividing the contents of the other between the two boxes with at least one chip in each box. There is a unique terminal position, namely (1, 1). Last player to move wins. Find all P-positions.
• Answer: The person who has an even pile available wins. The person who has two odd piles to work on loses.